{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "20c62837-5261-4604-acc4-bed8554b86dc",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/trapping-rain-water/\n",
    "\n",
    "\n",
    "Memory Limit Exceeded\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        #9:02\n",
    "        self.sum = 0\n",
    "        def conditionMatch(numbers: List[int]):\n",
    "            #print(numbers, self.sum)\n",
    "            if len(numbers) <= 2:\n",
    "                return\n",
    "            \n",
    "            startIndex = 0\n",
    "            startNumber = None\n",
    "            for index, number in enumerate(numbers):\n",
    "                if startNumber == None:\n",
    "                    startNumber = number\n",
    "                else:\n",
    "                    if number >= startNumber:\n",
    "                        self.sum += startNumber * (index - startIndex) - sum(numbers[startIndex: index])\n",
    "                        conditionMatch(numbers[index:])\n",
    "                        return\n",
    "                    \n",
    "            conditionMatch(list(reversed(numbers)))\n",
    "            \n",
    "        conditionMatch(height)\n",
    "        \n",
    "        return self.sum\n",
    "        #9:08\n",
    "        #debug until 9:20, 320 / 320 test cases passed, but took too much memory.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2d6354a-362a-480f-8050-d71f84888a67",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2445bb5f-a909-4684-a1dc-396f0fafb740",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "c5c8e3d8-7494-473a-a59b-935b956ce2bc",
   "metadata": {},
   "source": [
    "Success\n",
    "\n",
    "___\n",
    "\n",
    "Runtime\n",
    "397 ms\n",
    "\n",
    "Beats\n",
    "14.53%\n",
    "\n",
    "Memory\n",
    "16.2 MB\n",
    "\n",
    "Beats\n",
    "10.87%\n",
    "\n",
    "___\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 2022-12-1 02:49\n",
    "        def fast_found():\n",
    "            def find_blue_water(numbers, reversed=False):\n",
    "                if (reversed):\n",
    "                    numbers.reverse()\n",
    "    \n",
    "                blue_water_cell_counting = 0\n",
    "    \n",
    "                startIndex = 0\n",
    "                startNumber = numbers[0]\n",
    "    \n",
    "                index = 0\n",
    "                while index < len(numbers) and len(numbers) > 2:\n",
    "                    number = numbers[index]\n",
    "    \n",
    "                    if number >= startNumber:\n",
    "                        blue_water_cell_we_found = startNumber * (index - startIndex) - sum(numbers[startIndex: index])\n",
    "                        #print(numbers, (startIndex, index), (startNumber), blue_water_cell_we_found)\n",
    "                        blue_water_cell_counting += blue_water_cell_we_found\n",
    "    \n",
    "                        startIndex = index\n",
    "                        startNumber = number\n",
    "    \n",
    "                    index += 1\n",
    "                \n",
    "                return blue_water_cell_counting\n",
    "                        \n",
    "            numbers = height.copy()\n",
    "            result1 = find_blue_water(numbers, reversed=False)\n",
    "    \n",
    "            numbers = height.copy()\n",
    "            result2 = find_blue_water(numbers, reversed=True)\n",
    "            \n",
    "            return result1 + result2\n",
    "\n",
    "        if len(height) > 500:\n",
    "            return fast_found()\n",
    "        # 2022-12-1 05:10\n",
    "        # I think this version should work in all situation, but it didn't. for example, [2,0,2]\n",
    "        \n",
    "\n",
    "        #9:02\n",
    "        self.sum = 0\n",
    "        def conditionMatch(numbers: List[int]):\n",
    "            #print(numbers, self.sum)\n",
    "            length = 0\n",
    "            for i in numbers:\n",
    "                length += 1\n",
    "            if length <= 2:\n",
    "                return\n",
    "            \n",
    "            startIndex = 0\n",
    "            startNumber = None\n",
    "            for index, number in enumerate(numbers):\n",
    "                if startNumber == None:\n",
    "                    startNumber = number\n",
    "                else:\n",
    "                    if number >= startNumber:\n",
    "                        blue_water_cell_we_found = startNumber * (index - startIndex) - sum(numbers[startIndex: index])\n",
    "                        self.sum += blue_water_cell_we_found\n",
    "                        #print(numbers, (startIndex, index), startNumber, blue_water_cell_we_found)\n",
    "                        conditionMatch(numbers[index:])\n",
    "                        return\n",
    "                    \n",
    "            numbers.reverse()\n",
    "            #print(\"reversed\")\n",
    "            conditionMatch(numbers)\n",
    "            \n",
    "        conditionMatch(height)\n",
    "        \n",
    "        return self.sum\n",
    "        #9:08\n",
    "        #debug until 9:20, 320 / 320 test cases passed, but took too much memory.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca82dc4b-2d83-4a2f-ab6e-091d081c54e9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}